/*
 * graph.h
 *
 *  Created on: Dec 9, 2008
 *      Author: ketkar
 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <string>
#include <set>
#include <map>
#include <algorithm>
// This is gspan2
// This is gspan2
// This is gspan2
// This is gspan 1
// This is gspan2
// This is gspan2
// This is gspan2
// This is gspan 1 again!!!
// Vertex
// This is gspan2
// This is gspan2
// This is gspan2
// Vertex
// Vertex
class Vertex
{
public:
	Vertex(): id_(0), label_("") {}
	Vertex(int id, std::string label): id_(id), label_(label) {}
	void add_adjacent_vertex(int id) {adjacent_vertices.insert(id);}
	void add_incident_edge(int id) {incident_edges.insert(id);}
	int get_id() {return id_;}
	std::string get_label() {return label_;}
	std::set<int> get_adjacent_vertices() {return adjacent_vertices;}
	std::set<int> get_incident_edges() {return incident_edges;}
private:
	int id_;
	std::string label_;
	std::set<int> adjacent_vertices;
	std::set<int> incident_edges;
};

// This is the edge class !!!
class Edge
{
public:
	Edge():id_(0), vertex1_(0), vertex2_(0), label_("") {}
	Edge(int id, int vertex1, int vertex2, std::string label):
			id_(id), vertex1_(vertex1), vertex2_(vertex2), label_(label) {}
	int get_id() {return id_;}
	int get_vertex1() {return vertex1_;}
	int get_vertex2() {return vertex2_;}
	std::string get_label() {return label_;}
private:
	int id_;
	int vertex1_;
	int vertex2_;
	std::string label_;
};

class Graph
{
public:
	Graph(): vertex_count(0), edge_count(0) {}
	int get_vertex_count() {return vertex_count;}
	int get_edge_count() {return edge_count;}
	void add_vertex(Vertex vertex)
	{
		vertices.insert(std::pair<int, Vertex>(vertex.get_id(), vertex));
		if (matching_vertices.find(vertex.get_label()) == matching_vertices.end())
		{
			std::set<int> new_set;
			new_set.insert(vertex.get_id());
			matching_vertices.insert(std::pair<std::string,std::set<int> >(vertex.get_label(), new_set));
		}
		else
		{
			(matching_vertices[vertex.get_label()]).insert(vertex.get_id());
		}
		vertex_count++;
	}
	void add_edge(Edge edge)
	{
		edges.insert(std::pair<int, Edge>(edge.get_id(), edge));
		edge_count++;
	}
	Vertex& get_vertex(int id) { return vertices[id];}
	Edge& get_edge(int id) { return edges[id];}
	bool check_edge_present(int vertex_id1, int vertex_id2, std::string label)
	{
		Vertex vertex1 = get_vertex(vertex_id1);
		Vertex vertex2 = get_vertex(vertex_id2);
		std::set<int> vertex1_incident_edges = vertex1.get_incident_edges();
		std::set<int> vertex2_incident_edges = vertex2.get_incident_edges();
		std::set<int> intersection_result;
		set_intersection(vertex1_incident_edges.begin(),
						 vertex1_incident_edges.end(),
						 vertex2_incident_edges.begin(),
						 vertex2_incident_edges.end(),
						 inserter(intersection_result, intersection_result.begin()));
		if (intersection_result.empty())
			return false;
		else
		{
			Edge edge = get_edge(*(intersection_result.begin()));
			if (edge.get_label() == label)
				return true;
			else
				return false;
		}
	}
	std::set<int>& get_matching_vertices(std::string label)
	{
		return matching_vertices[label];
	}
	void dump()
	{
		for(int vertex_id = 1; vertex_id <= vertex_count; vertex_id++)
		{
			Vertex vertex = get_vertex(vertex_id);
			std::cout << vertex_id << " " << vertex.get_label() << "\n";
		}

		for(int edge_id = 1; edge_id <= edge_count; edge_id++)
		{
			Edge edge = get_edge(edge_id);
			std::cout << edge_id << " ";
			std::cout << edge.get_vertex1() << " ";
			std::cout << edge.get_vertex2() << " ";
			std::cout << edge.get_label() << "\n";
		}
	}
private:
	int vertex_count;
	int edge_count;
	std::map<int, Vertex> vertices;
	std::map<int, Edge> edges;
	std::map<std::string, std::set<int> >matching_vertices;
};

class DFS
{
public:
	DFS(Graph& given): graph(given) {}
	void dump() { graph.dump(); }
private:
	Graph& graph;
};
#endif /* GRAPH_H_ */
